package com.leetcode.solution.s8x;

import java.util.ArrayDeque;
import java.util.Deque;

public class LargestRectangleArea84 {
    public static void main(String[] args) {
        int[] heights = { 2, 1, 5, 6, 2, 3 };
        int result = new LargestRectangleArea84().largestRectangleArea(heights);

        System.out.println(result);
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        } else if (heights.length == 1) {
            return heights[0];
        }

        int[] newHeights = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }

        heights = newHeights;
        Deque<Integer> heightStack = new ArrayDeque<>();
        heightStack.addLast(0);
        int res = 0;
        for (int idx = 1; idx < heights.length; idx++) {
            while (heights[idx] < heights[heightStack.peek()]) {
                int currIdx = heightStack.pop();

                res = Math.max(res, heights[currIdx] * (idx - heightStack.peek() - 1));
            }

            heightStack.push(idx);
        }

        return res;
    }
}
